package com.kobeliu.entity;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/6 13:42
 */

/**
 * 层序遍历就行
 *
 * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 *
 * 例如：
 *
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 返回它的最大深度 3 。
 */
public class Demo_70_sword_55_1 {

    public int maxDepth1(TreeNode root) {
        //空记得判断
        if(root==null) return 0;
        int n = 1;
        int height = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode poll;

        while(queue.size()!=0){
            poll = queue.poll();
            if(poll.left!=null) queue.add(poll.left);
            if(poll.right!=null) queue.add(poll.right);
            if(--n==0){
                height++;
                n = queue.size();
            }
        }

        return height;

    }

    public int maxDepth(TreeNode root) {
        return root == null?0:Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
